//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//#include <stdbool.h>
//#include <stdlib.h> 
//#include <assert.h>
//typedef char STDataType;
//
//typedef struct stack {
//    STDataType* a;
//    int capacity;
//    int size;
//} Stack;
//
//void StackInit(Stack* ps) {
//    ps->a = NULL;
//    ps->capacity = ps->size = 0;
//}
//
//void StackPush(Stack* ps, STDataType data) {
//    assert(ps);
//    if (ps->size == ps->capacity) {
//        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//        STDataType* tmp =
//            (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
//        if (tmp == NULL) {
//            perror("realloc fail");
//            return;
//        }
//        else {
//            ps->a = tmp;
//            ps->capacity = newcapacity;
//        }
//    }
//    ps->a[ps->size] = data;
//    ps->size++;
//}
//
//void StackPop(Stack* ps) {
//    assert(ps);
//    assert(ps->size > 0);
//    ps->size--;
//}
//
//int StackSize(Stack* ps) {
//    assert(ps);
//    return ps->size;
//}
//STDataType StackTop(Stack* ps) {
//    assert(ps);
//
//    int size = ps->size - 1;
//    return ps->a[size];
//}
//
//bool StackEmpty(Stack* ps) {
//    assert(ps);
//    if (StackSize(ps) == 0) {
//        return true;
//    }
//    else {
//        return false;
//    }
//}
//
//void StackDestroy(Stack* ps) {
//    assert(ps);
//    free(ps->a);
//    ps->a = NULL;
//    ps->size = ps->capacity = 0;
//}
//
//bool isValid(char* s) {
//    Stack st;
//    StackInit(&st);
//
//
//    while (*s) {
//        if (*s == '(' || *s == '[' || *s == '{') {
//            StackPush(&st, *s);
//        }
//        else {
//            if (StackEmpty(&st)) {
//                StackDestroy(&st);
//                printf("false\n");
//                return false;
//            }
//            char left = StackTop(&st);
//            StackPop(&st);
//
//            if ((left == '(' && *s != ')') || (left == '{' && *s != '}') ||
//                (left == '[' && *s != ']')) {
//                StackDestroy(&st);
//                printf("false\n");
//                return false;
//            }
//        }
//        ++s;
//    }
//    bool ret = StackEmpty(&st);
//    StackDestroy(&st);
//    if (ret) {
//        printf("true\n");
//    }
//    else {
//        printf("false\n");
//    }
//    return ret;
//}
//
//
//int main() {
//    char s1[] = "()";
//    char s2[] = "(]";
//    char s3[] = "([])";
//    char s4[] = "(){}[]";
//        
//    isValid(&s1);
//   isValid(&s2);
//   isValid(&s3);
//    isValid(&s4);
//
//
//
//    return 0;
//}